package com.hot100.mid;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 单词拆分
 * @date 2022/8/28 16:25
 */
public class Demo31 {
    public static void main(String[] args) {
        String s="cars";
        List<String> wordDict =new ArrayList<>();
        wordDict.add("rs" );
        wordDict.add("ca" );
        wordDict.add("car" );
        System.out.println(wordBreak(s, wordDict));


    }
    public static boolean wordBreak1(String s, List<String> wordDict) {
        if(s.length()==0){
            return true;
        }
        for (String s1 : wordDict) {
            if (s.startsWith(s1)) {
               s=s.substring(s1.length());
                if (wordBreak(s,wordDict)) {
                    return true;
                }
            }
        }
        return false;
    }


    public static boolean wordBreak(String s, List<String> wordDict) {
      int length=s.length();
      //表示可以boolean[i] 表示 s 中索引为 [0,  i - 1] 是否可以从(0,i) 可以通过1个或者多个可以匹配到
      boolean[]  reachLetter=new boolean[length+1];
      //reachLetter[1]表示第一个索引0，所以reachLetter[0]为默认匹配到的空字符串
      reachLetter[0]=true;
        //从第一个字母开始匹配,到最后一个字母
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                if(reachLetter[j]&&wordDict.contains(s.substring(j,i))){
                    // reachLetter[j]表示 j索引这个位置可以到达； 1
                    // wordDict.contains(s.substring(j,i)) 表示含有j,i的字符串  2
                    // 满足1合2，表示 可以到达0，i的字符串拼接，最后返回只需要判断最后一个字母能否到达即可
                    reachLetter[i]=true;
                    break;
                }
            }
        }
        return reachLetter[length];
    }
}
